package com.mashibing.class07;

// 测试链接：https://leetcode.com/problems/balanced-binary-tree
public class Code02_BalancedBinaryTree {

    public static class TreeNode {
        public int val;
        public TreeNode left;
        public TreeNode right;

        TreeNode(int val) {
            this.val = val;
        }
    }

    // 返回两个信息的因子
    // isBalanced : 整体是否是平衡树
    // 以某个节点头的时候,
    // 1) 整棵树是否平衡
    // 2) 整棵树的高度是多少.
    public static class Info {
        public boolean isBalanced;
        public int height;

        public Info(boolean i, int h) {
            isBalanced = i;
            height = h;
        }
    }

    public static boolean isBalanced(TreeNode root) {
        return process(root).isBalanced;
    }

    public static Info process(TreeNode root) {
        if (root == null) { // 空树是平衡的, 且高度为0
            return new Info(true, 0);
        }
        //分别求出左树 和 右树 是否整体平衡且高度信息.
        Info leftInfo = process(root.left);
        Info rightInfo = process(root.right);
        //求root树的高度和平衡信息.
        int height = Math.max(leftInfo.height, rightInfo.height) + 1;
        boolean isBalanced = leftInfo.isBalanced && rightInfo.isBalanced
                && Math.abs(leftInfo.height - rightInfo.height) < 2;
        return new Info(isBalanced, height);
    }

}
